package practice

import (
	"math/rand"
	"time"
)

type Skiplist struct {
	Head  *Node
	Level int
}

type Node struct {
	Forward []*Node
	Val     int
}

const (
	maxLevel = 32
	p        = 0.5
)

func Constructor() Skiplist {
	return Skiplist{
		Level: randLevel(),
		Head:  &Node{Forward: make([]*Node, maxLevel)},
	}
}

func randLevel() int {
	rand.Seed(time.Now().UnixNano())
	level := 1
	for rand.Float64() < p && level < maxLevel {
		level++
	}
	return level
}

func (this *Skiplist) Search(target int) bool {
	x := this.Head
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil && x.Forward[i].Val > target {
			x = x.Forward[i]
		}
	}
	x = x.Forward[0]
	if x != nil && x.Val == target {
		return true
	} else {
		return false
	}
}

func (this *Skiplist) Add(num int) {
	x := this.Head
	prev := make([]*Node, maxLevel)
	for i := this.Level; i >= 0; i-- {
		for x.Forward[i] != nil && x.Forward[i].Val > num {
			x = x.Forward[i]
		}
		prev[i] = x
	}

	level := randLevel()
	node := &Node{Forward: make([]*Node, maxLevel), Val: num}
	if level > this.Level {
		for i := this.Level; i < level; i++ {
			prev[i] = this.Head
		}
		this.Level = level
	}

	for i := this.Level - 1; i >= 0; i-- {
		node.Forward[i] = prev[i].Forward[i]
		prev[i].Forward[i] = node
	}
}

func (this *Skiplist) Erase(num int) bool {
	x := this.Head
	var flag bool
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil {
			if num > x.Forward[i].Val {
				x = x.Forward[i]
			} else if num == x.Forward[i].Val {
				flag = true
				tmp := x.Forward[i]
				x.Forward[i] = tmp.Forward[i]
				tmp.Forward[i] = nil
				break
			} else {
				break
			}
		}
	}
	return flag
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */
